Systems that determine whether to make synonym substitutes based on contexts of co-occurring query terms often have a hard time learning good synonym rules for contexts that appear very infrequently. For example, learning that “restaurants” is a good synonym for “food” in the query [food in San Francisco] is relatively straightforward, because the volume of query traffic including the query term “San Francisco” is very large. For much smaller cities, such as Grey Bull, Wyo., the query stream may have never seen any supporting evidence for this synonym substitution.